#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
int c,T,n,k,dp[N][N],a[N],b[N],ans;
int d[N],f[N];
priority_queue<pair<int,int> > q;
signed main() {
	freopen("festival.in","r",stdin);
	freopen("festival.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>c>>T;
	while(T--) {
		cin>>n>>k;
		for(int i=1;i<n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) d[i]=0;
		for(int i=1;i<=k;i++) {
			cin>>b[i];
			for(int j=i;j<=n-k+i;j++) d[j]+=b[i];
		}
		while(!q.empty()) q.pop();
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=5000;j++) {
				if(i==1) dp[i][j]=j*d[i];
				else {
					while(!q.empty()&&q.top().second+j>a[i-1]) q.pop();
					if(q.empty()) break ;
					dp[i][j]=q.top().first+j*d[i];
				}
			}
			while(!q.empty()) q.pop();
			for(int j=0;j<=5000;j++) q.push(make_pair(dp[i][j],j));
		}
		cout<<q.top().first<<"\n";
	}
	return 0;
}
/*
0 2
4 2
5 4 2
2 1
7 4
4 8 6 7 8 3
3 5 1 2
*/
